package bin_tree.leetcode;

import java.util.Scanner;

/**
 * 根据前序遍历结果构建二叉树
 * @author yuisama
 * @date 2022/02/23 19:55
 **/
public class NowCoder_BuildTree {
    private static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;
        TreeNode() {
        }

        TreeNode(char val) {
            this.val = val;
        }

        TreeNode(char val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    // index表示当前前序遍历处理到哪个字符了
    private static int index = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 多组输入
        while (scanner.hasNext()) {
            // 每次读取一行前序遍历的结果
            String str = scanner.next();
            // 根据前序遍历的字符串构建二叉树
            TreeNode root = preOrderBuild(str);
            // 对其使用中序遍历，输出节点值
            inOrder(root);
            // 每行输出独占一行
            System.out.println();
            index = 0;
        }
    }

    /**
     * 根据前序遍历的字符串来构建二叉树
     * @param str
     * @return
     */
    private static TreeNode preOrderBuild(String str) {
        char cur = str.charAt(index);
        if (cur == '#') {
            return null;
        }
        TreeNode root = new TreeNode(cur);
        index ++;
        root.left = preOrderBuild(str);
        index ++;
        root.right = preOrderBuild(str);
        return root;
    }

    private static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先递归左子树
        inOrder(root.left);
        // 根
        System.out.print(root.val + " ");
        // 再右子树
        inOrder(root.right);
    }
}